package com.wfm.niuke.binsearch;

import java.util.Arrays;
import org.junit.Test;

/**
 * 方法一：归并排序，
 * 在归并的时候计算逆序对，不过首先你得写出归并排序来，
 * 首先为了避免更改原数组，copy一份，然后为了归并排序，需要再nwe一个数组，然后就传入一个方法x
 * 这个x方法作用就是：除以2；然后递归；然后判断左子数组最大是否小于右子数组最小，是，放回左右子数组的逆序对相加；否则进一步处理y
 * y的话就是对存在左子数组最大大于右子数组最小的情况了
 * 比如：【11,20,25,29,30,   10,15,20,35,40】
 *        30左子数组最大 i     j 右子数组最小10
 */
public class BM20ReversePairsO51 {
    public int reversePairs(int[] nums) {
        return 0;
    }
    @Test
    public void test(){
        reversePairs(new int[]{7,5,6,4});
    }
    @Test
    public void test2(){
        mergeAndCount(new int[]{11,20,25,29,30,10,15,20,35,40},0,4,9,new int[10]);
    }
    int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {

            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }

    class BIT {
        private int[] tree;
        private int n;

        public BIT(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public int lowbit(int x) {
            return x & (-x);
        }

        public int query(int x) {
            int ret = 0;
            while (x != 0) {
                ret += tree[x];
                x -= lowbit(x);
            }
            return ret;
        }

        public void update(int x) {
            while (x <= n) {
                ++tree[x];
                x += lowbit(x);
            }
        }
    }

    public int reversePairs2(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];
        System.arraycopy(nums, 0, tmp, 0, n);
        // 离散化
        Arrays.sort(tmp);
        for (int i = 0; i < n; ++i) {
            nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
        }
        // 树状数组统计逆序对
        BIT bit = new BIT(n);
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            // 例子：2 6 4 8 3
            //这时万恶的一句代码，理解了半天。你首先要知道bit的query参数是找到输入参数的总和，
            // nums[i]这里已经不是原数组了，是排名了，所以比如nums[i]=5，-1就等于4，
            // 比如元素8排名在第5位，减一变4，就是代表查找排名在前4位的，前4位都比自己小，所以换一个角度，就是找到比自己8小的元素个数总和
            // 因为是从右往左遍历，所以比8小的只有3，为什么没有2 6 4？因为他们还没入bit数组，所以bit数组里都还没他们记录呢，
            // 所以，对于一个2 6 4 8 3 这样的序列，我只需要：
            // 看3，你右边有没有比我小的？有就加比我小的个数，没有就下个数
            // 看8，8右边有没有比我小的，有，并且比他小的个数就一个3。所以结果+1
            // 一直到6， 看右边有没有比我小的，有4和3，那么，就需要＋2
            // 至于怎么样计算看右边有没有比我小的，你不是根据大小排序了吗。我排第5，那排第4的就比我小啊，从小到大排序
            // 会不会判断到左边去，比如6 我去看到左边2去了，答案是不会，因为你是从右往左遍历进入bit数组的啊，所以bit数组只记录了右边的排名个数
            // md，就是排名这个搞得头晕，以为排名第4，那肯定比排名第5厉害啊，就更大啊，拜托这是从小到大排，不是排成绩啦！！
            // 另外就是 树状数组是真的难理解，虽然好用，但是设个设计不好理解。
            // 参考https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solution/shu-zhuang-shu-zu-by-liweiwei1419/
            ans += bit.query(nums[i] - 1);
            bit.update(nums[i]);
        }
        return ans;
    }
    @Test
    public void test3(){
        System.out.println(reversePairs2(new int[]{2, 6, 4, 8, 3}));
    }
}
